package oj;

/**
 * @author 郝文雪
 * @date 2022/9/12 16:53
 * @Description Test
 */
public class LC518 {
    public int change(int amount, int[] coins) {
        int n=coins.length;
        int[][] dp=new int[n+1][amount+1];
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            int value=coins[i-1];
            for(int j=0;j<=amount;j++){
                dp[i][j]=dp[i-1][j];
                for(int k=1;j>=k*value;k++){
                    dp[i][j]+=dp[i-1][j-k*value];
                }
            }
        }
        return dp[n][amount];
    }

    //一维数组
//    public int change(int amount, int[] coins) {
//        int n=coins.length;
//        int[] dp=new int[amount+1];
//        dp[0]=1;
//        for(int i=0;i<n;i++){
//            int value=coins[i];
//            for(int j=value;j<=amount;j++){
//                dp[j]+=dp[j-value];
//
//            }
//        }
//
//        return dp[amount];
//    }
}
